Форум dkLab и Denwer
Здесь общаются Web-разработчики.
Генеральный спонсор:
Хостинг «Джино»

Дерево для CMS (Maximark)
Author Message
Maximark
Участник форума



Joined: 04 Apr 2006
Posts: 43
Карма: 1
   поощрить/наказать


PostPosted: Thu Nov 23, 2006 4:42 pm (написано за 9 минут 46 секунд)
   Post subject: Дерево для CMS
Reply with quote

Знаю заезженная тема, но...

Никак не могу выбрать алгоритм для cms (Nested sets не тыкать сразу :) )

суть такая:

база (иерхарическая стурктура)

`id` | `pid` | `page` | `order'

Задачи:
- вывод всего дерева с LIMIT с сортировкой по `order`, где `order` в пределах ветки

например

1 | 0 | products | 1
2 | 0 | about | 2
3 | 0 | contact | 3
4 | 1 | photo | 1
5 | 1 | comp | 2
6 | 2 | awards | 1
7 | 0 | faq | 1
...
1000000 | 0 | qwer | 1

При LIMIT 0,5

Должно быть

products
| |_ photo
| |_ comp
|
about
| |_ awards
|

т.е. в основном выводится только часть дерева

Какой алгоритм выбрать?

Вложенность я думаю максимум 5
а вот нод может быть много
Back to top
View user's profile Send private message
amikhailov
Участник форума



Joined: 11 Nov 2004
Posts: 180
Карма: 4
   поощрить/наказать

Location: Екатеринбург

PostPosted: Fri Nov 24, 2006 3:30 pm (спустя 22 часа 48 минут; написано за 4 минуты 2 секунды)
   Post subject:
Reply with quote

А вы попробуйте завести еще одну колонку, в которой указывался бы порядок вывода общего дерева. `order_total` например. И еще `depth` - глубина вложенности.

Тогда будет выводить совсем просто:
Code (SQL): скопировать код в буфер обмена
SELECT * FROM yourtable ORDER BY total_order ASC LIMIT 5
При изменении таблицы рассчитывать этот самый `total_order` не так уж сложно.

Если бы СУБД была не mysql, а oracle, то этого бы не потребовалось - там есть механизм обхода иерархических структур. Но я так смекаю, что используется именно mysql
Back to top
View user's profile Send private message
Maximark
Участник форума



Joined: 04 Apr 2006
Posts: 43
Карма: 1
   поощрить/наказать


PostPosted: Fri Nov 24, 2006 4:08 pm (спустя 38 минут; написано за 12 минут 19 секунд)
   Post subject:
Reply with quote

Да используется MySQl

Тяжко будет тогда при переносе дерева (придется все записи после вставки изменять)... но это используется редко.

Есть еще вариант www.sql.ru/articles/mssql/2005/061904TreesInSQLdatabases.shtml

или php.com.ua/forum/viewtopic.php?p=48287#48287

т.е.


Сейчас будете смеятся.... но так реализовано дерево в бухгалтерской программе Акцент

суть такая

имеем id и создается таблица где на каждый уровень свой pid т.е. вся структура дерева известна. т.к. вложенностей у нас не так и много ~5-6

т.е. таблица будет

id | order | pid1 | pid2 | pid3| pid4| pid5|

(если вложенность требуется еще, ничего страшного - добавляется еще колонка)


т.е. я не буду цифрами, потому как не понятно.
Code (any language): скопировать код в буфер обмена
id |  label |
1    about
2    products
3    faq
4    contacts
5    awards
6    comp
7    photo
8    vote
9    video
10   hdd
... и т д

теперь вторая таблица соответственно вместо слов(для ясности) будут id
Code (any language): скопировать код в буфер обмена
id     | order |   pid1     |     pid2    |
 about      1
 products   2
 faq        3
 contacts   4
 awards     1    about
 comp       1    products
 photo      2    products
 vote       1    faq
 video      1    products        comp
 hdd        2    products        comp
и исходя из неё мы сразу всё видим.

Смешно, но очень быстро. Даже когда мы переносим ветку мы изменяем фактически одну запись (макс 2 записи если в середину дерева).

для каждой записи мы видим количесво вложений и на каком уровне запись и как сортировать

Я в начале смеялся, когда мне это сказали и показали в Акценте. Но и запрос простой для любой манипуляции с деревом, и самое главное очень быстро, и памяти не жрет много. Единственно, каждый запрос немного громоздкий (но быстрый)

Как вам такой подход ???

Вообще MySQl и иерархические структуры это такой себе трабл.

Last edited by Maximark on Fri Nov 24, 2006 4:21 pm; edited 2 times in total
Back to top
View user's profile Send private message
amikhailov
Участник форума



Joined: 11 Nov 2004
Posts: 180
Карма: 4
   поощрить/наказать

Location: Екатеринбург

PostPosted: Fri Nov 24, 2006 4:14 pm (спустя 5 минут; написано за 1 минуту 51 секунду)
   Post subject:
Reply with quote

Неуниверсальный подход какой-то... Лучше уж комбинировать nested sets, и id/parent_id, имхо. Пересчет дерева nested sets - несложная задача и об этом много где написано. Поищите гуглом/яндексом. Получите хорошее быстродействие
Back to top
View user's profile Send private message
Maximark
Участник форума



Joined: 04 Apr 2006
Posts: 43
Карма: 1
   поощрить/наказать


PostPosted: Fri Nov 24, 2006 4:25 pm (спустя 10 минут; написано за 47 секунд)
   Post subject:
Reply with quote

Да вот Nested Sets за.ё.живается на большом количестве нод. (во всяком случае так пишут)
Back to top
View user's profile Send private message
amikhailov
Участник форума



Joined: 11 Nov 2004
Posts: 180
Карма: 4
   поощрить/наказать

Location: Екатеринбург

PostPosted: Sun Nov 26, 2006 2:51 pm (спустя 1 день 22 часа 26 минут; написано за 22 секунды)
   Post subject:
Reply with quote

Не знаю, откуда у вас такая информация.
Back to top
View user's profile Send private message
Maximark
Участник форума



Joined: 04 Apr 2006
Posts: 43
Карма: 1
   поощрить/наказать


PostPosted: Tue Nov 28, 2006 1:31 am (спустя 1 день 10 часов 40 минут; написано за 8 минут 4 секунды)
   Post subject:
Reply with quote

Что-то очень тихо. Неужели никого не интересует иерархические структуры.
Как все же вы относитесь к тому чтобы хранить всё дерево в отдельной таблице. Подобие файловой системы (типа FAT)
Причем я склоняюсь к мнению, что хранить именно путями, тогда необходимость в LIKE forum.dklab.ru/sql/php/IerarhicheskieStrukturiVBd.html отпадет. Честно говоря подсчет количества COUNT занимающего с вложенностью 20 почти 3 сек. уж очень много. А если нагрузка на сервер?

Неужели ни у кого нет нормального алгоритма для ИС?
Критерии базы:
1. порядка 1М записей, может до 10 М
2. вложенность порядка 30 (макс, в среднем 10)
3. экономим память сервера :)
4. подсчет общего кол-ва результатов (для пейджинга)
4. Обычно общее количество будет в районе 1000 (макс)

Выодится порядка 20 результатов на страницу(макс)
Back to top
View user's profile Send private message
Kupuyc
Участник форума



Joined: 31 Mar 2006
Posts: 146
Карма: 5
   поощрить/наказать


PostPosted: Tue Nov 28, 2006 7:22 am (спустя 5 часов 50 минут; написано за 34 секунды)
   Post subject:
Reply with quote

Так ведь довольно неплохой тред по деревьям уже есть... причем на одой странице с Вашим.
Back to top
View user's profile Send private message
amikhailov
Участник форума



Joined: 11 Nov 2004
Posts: 180
Карма: 4
   поощрить/наказать

Location: Екатеринбург

PostPosted: Tue Nov 28, 2006 7:55 am (спустя 33 минуты; написано за 28 секунд)
   Post subject:
Reply with quote

Maximark
Почитайте вот это web-notes.ru/articles/nested-sets/
Back to top
View user's profile Send private message
Phoebus
Участник форума



Joined: 16 Nov 2003
Posts: 30
Карма: 1
   поощрить/наказать

Location: Minsk

PostPosted: Tue Nov 28, 2006 3:26 pm (спустя 7 часов 30 минут; написано за 3 минуты 2 секунды)
   Post subject:
Reply with quote

Maximark wrote:
Честно говоря подсчет количества COUNT занимающего с вложенностью 20 почти 3 сек. уж очень много. А если нагрузка на сервер?
Кэшируйте количество вложенных элементов (добавить поле node_elts_number, к примеру). И при каждом добавлении/удалении узла обновляйте node_elts_number всех родительских.
Nested sets вообще идеален для работы с большими деревьями (где наибольшая нагрузка -- на его вывод из базы и т.д. -- т.е. там где используется SELECT, а не INSERT/UPDATE).
Вообще да, мне кажется, что все аспекты adjacency matrix vs nested sets были вполне нормально освещены здесь (forum.dklab.ru/sql/php/IerarhicheskieStrukturiVBd.html).
Back to top
View user's profile Send private message Send e-mail
Dark-Demon
Участник форума
Banned


Joined: 04 Feb 2007
Posts: 45
Карма: -3
   поощрить/наказать

Location: spb

PostPosted: Wed Feb 07, 2007 12:53 am (спустя 2 месяца 8 дней 9 часов 27 минут)
   Post subject:
Reply with quote

Quote:
Как все же вы относитесь к тому чтобы хранить всё дерево в отдельной таблице.
да, так и надо. структуру надо отделять от контента. хотябы даже потому, что при изменении структуры не нужно было копировать туда-сюда и весь контент.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic All times are GMT + 3 Hours
Page 1 of 1    Email to a Friend.
You cannot post new topics in this forum. You cannot reply to topics in this forum. You cannot edit your posts in this forum. You cannot delete your posts in this forum. You cannot vote in polls in this forum. You cannot attach files in this forum. You can download files in this forum.
XML